// 假设二叉树采用二叉链表存储。利用先序扩展序列请编写程序，判断一棵二叉树是否为正则树。所谓一棵二叉树为正则二叉树，是指二叉树中各结点的度要么为0，要么为2。请编写函数完成以上功能，在主函数中调用上述函数实现上述操作。若是正则树，则输出“YES”，否则输出“NO”。
// 输入：dac##eg##h##b##

// 输出：YES

// 输入：dac##eg##h##b#f##

// 输出：NO

#include <iostream>
#include <stack>
#include <cstdio>
#define MAXSIZE 1000
using namespace std;
typedef struct BiTnode 
{
	char data;
	struct BiTnode *lchild, *rchild;
}BiNode,*Bitree;

Bitree creatbitree()//递归法先序建立二叉树
{
    Bitree T;
    char ch;
    //cin >> ch;
    scanf("%c", &ch);
    if(ch=='#')
        T = NULL;
    else
    {
        T = new BiNode;
        T->data = ch;
        T->lchild = creatbitree();
        T->rchild = creatbitree();
    }
    return T;
}

int zztree(Bitree T)
{
	if(!T)//空结点
	   return 1;
	else if(!T->lchild&&!T->rchild)//叶子结点（左右孩子都空）
	  return 1;
	else if(T->lchild&&T->rchild)//左右孩子都不为空
	{
		if(zztree(T->lchild)&&zztree(T->rchild))
			return 1;
		else
		return 0;
	}
	else//左右孩子一空一不空
	return 0;
}

int main()
{
    int flag;
	Bitree T;
    T=creatbitree();
    flag = zztree(T);
    if(flag==1)
    cout << "YES";
    else
    cout << "NO";
    return 0;
}
